/*
 * @lc app=leetcode.cn id=449 lang=typescript
 *
 * [449] 序列化和反序列化二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

/*
 * Encodes a tree to a single string.
 */
// 广义码
function serialize(root: TreeNode | null, res: Array<number | string> = []): string {
  if (root === null) return '';
  res.push(root.val);
  if (root.left === null && root.right === null) return res.join('');
  res.push('(');
  serialize(root.left, res);
  if (root.right) {
    res.push(',');
    serialize(root.right, res);
  }
  res.push(')');
  return res.join('');
}

/*
 * Decodes your encoded data to tree.
 */
// 自动机
function deserialize(data: string): TreeNode | null {
  const stack = [];
  let scode = 0;
  let idx = 0;
  let childType = 0;
  let root = null;
  let p = root;
  while (idx < data.length) {
    switch (scode) {
      case 0: {
        if (data[idx] >= '0' && data[idx] <= '9') scode = 1;
        else if (data[idx] === '(') scode = 2;
        else if (data[idx] === ',') scode = 3;
        else if (data[idx] === ')') scode = 4;
        break;
      }
      case 1: {
        // 处理数字
        let num = 0;
        while (idx < data.length && data[idx] >= '0' && data[idx] <= '9') {
          num = num * 10 + Number(data[idx]);
          idx++;
        }
        p = new TreeNode(num);
        // 如果根节点为空，将p赋值给根节点
        root === null && (root = p);
        // 处理左节点
        childType === 1 && (stack[stack.length - 1].left = p);
        // 处理右节点
        childType === 2 && (stack[stack.length - 1].right = p);
        scode = 0;
        break;
      }
      case 2: {
        // 处理左括号
        idx++;
        stack.push(p);
        childType = 1;
        scode = 0;
        break;
      }
      case 3: {
        // 处理逗号，也就是右节点
        idx++;
        childType = 2;
        scode = 0;
        break;
      }
      case 4: {
        idx++;
        stack.pop();
        scode = 0;
        break;
      }
    }
  }
  return root;
}

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
// @lc code=end
